//折半查找

#pragma once

//在有序数组 a[n] 中查找 x
//若找到返回下标，否则返回-1
template <typename E>
int BinarySearch(E a[], int n, E x)
{
    int low = 0;
    int high = n - 1;
    while (low <= high)
    {
        //在 a[low..high]子序列中查找
        int min = (low + high) / 2;
        if (x == a[mid])
            return i;
        else if (x < a[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }

    return -1;
}


//在有序序列 a[low...high] 中查找 x (递归)
//若找到返回下标，否则返回-1
template <typename E>
int BinarySearch(E a[],int low,int high,E x)
{
    //当待查找序列 a[low...high] 为空时，找不到X
    if(low > high) //序列为空
       return -1;
    
    int mid = (low +high) / 2;
    if(x == a[mid])
       return mid;
    else if(x < a[mid])
        return BinarySearch(a.low,mid - 1,x);
    else 
        return BinarySearch(a.mid + 1,high,x);
}